package com.chj.jz.dp.class03;

//https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iv/description
public class Code08_BestTimetoBuyandSellStockIV {
	/**
	 * @param prices:
	 *            Given an integer array
	 * @return: Maximum profit
	 */
	public static int maxProfitIV(int K, int[] prices) {
		// write your code here

		int n = prices.length;
		if (n == 0) {
			return 0;
		}

		int i, j;
		if (K > n / 2) {
			int sum = 0;
			for (i = 0; i < n - 1; i++) {
				if (prices[i + 1] > prices[i]) {
					sum += prices[i + 1] - prices[i];
				}
			}

			return sum;
		}

		int[][] f = new int[2][2 * K + 2];
		int old, now = 0;

		f[now][1] = 0;
		for (i = 2; i <= 2 * K + 1; i++) {
			f[now][i] = Integer.MIN_VALUE;
		}

		for (i = 1; i <= n; i++) {
			old = now;
			now = 1 - now;

			for (j = 1; j <= 2 * K + 1; j += 2) {
				f[now][j] = f[old][j];
				if (j > 1 && i >= 2 && f[old][j - 1] != Integer.MIN_VALUE) {
					f[now][j] = Math.max(f[now][j], f[old][j - 1] + prices[i - 1] - prices[i - 2]);
				}
			}

			for (j = 2; j <= 2 * K; j += 2) {
				f[now][j] = f[old][j - 1];
				if (i >= 2 && f[old][j] != Integer.MIN_VALUE) {
					f[now][j] = Math.max(f[now][j], f[old][j] + prices[i - 1] - prices[i - 2]);
				}
			}
		}

		int res = Integer.MIN_VALUE;
		for (i = 1; i <= 2 * K + 1; i += 2) {
			res = Math.max(res, f[now][i]);
		}

		return res;
	}

	public static void main(String[] args) {
		{
			int k = 2;
			int[] arr = new int[] { 4, 4, 6, 1, 1, 4, 2, 5 };
			System.out.println(maxProfitIV(k, arr));
		}
		{
			int k = 1;
			int[] arr = new int[] { 3, 2, 1 };
			System.out.println(maxProfitIV(k, arr));
		}
		// {
		// int[] arr = new int[] { 1, 2, 3, 4, 5 };
		// System.out.println(maxProfitIII(arr));
		// }
		// {
		// int[] arr = new int[] { 5, 4, 3, 2, 1 };
		// System.out.println(maxProfitIII(arr));
		// }

	}
}
